1. Field of the Invention
This invention relates to digital image processing methods and more particularly to methods for encoding and decoding image data involving pattern frequencies such as binary halftones.
2. Prior Art
The standard international data transmission CCITT Group 3 MR and Group 4 MMR two-dimensional data compression schemes contain Modified Huffman code tables which were optimized for compressing text and line drawings. However, binary halftone representations of continuous tone images have a very different distribution of run sizes and occurrence of vertical references from such drawings. As a result, the amount of data required to represent these halftone images in "compressed" form may be greater than the amount of data required to represent the original image when these compression schemes or other currently used compression techniques are used. This expansion can be limited to about 1.15 by using "uncompressed mode". However, by definition, this mode does not give any compression.
Some examples of prior systems for dealing with the compression of halftone image data are found in U.S. Pat. No. 4,144,547 to STOFFEL and U.S. Pat. No. 4,559,563 to JOINER, which describe processes for coding mixed (text and halftone) documents using multiple-predictor systems with sets of predefined predictors. STOFFEL teaches the use of each available predictor to predict each unit of input data whereby the best predictor is selected, its identity is encoded, and the unit of data is then encoded using that predictor. The decoder gets an indication from the compressed data stream as to which predictor is to be used to decode each unit of data. JOINER uses the predictor which would have performed best on the previous unit of data to predict the pel values for the current unit of data (so that the identity of the predictor to be used does not have to be transmitted). It will be seen that these teachings are general approaches to the problem of efficiently compressing halftones and are not simple extensions of, but rather would be substituted for, the well known standard bilevel compression algorithms (CCITT G3/G4).
U.S. Pat. No. 4,355,306 to MITCHELL also describes a generic bilevel image coder/decoder system. While this system performs well on halftones, it similarly would not operate as a simple extension of the standard bilevel compression algorithms or other commonly-used techniques.
Other examples are found in U.S. Pat. No. 4,571,634 to CANESCHI ET AL which describes a coder/decoder for bilevel and halftoned images in which the halftones are formed by having areas of strict alternation of black and white pels, thus restricting its applicability; U.S. Pat. No. 4,425,582 to KADAKIA ET AL and U.S. Pat. No. 4,435,726 to LIAO which disclose an efficient hardware implementation for a specific predictor that is designed to work well on both text and halftone data wherein the predictor and a corresponding de-predictor would be added to an encoder/decoder system, such as that defined by the CCITT G3/G4 standards, to produce a version of the original data altered by a predictor scheme; and U.S. Pat. No. 4,193,096 to STOFFEL which shows a system that scans and halftones an image and then compresses the resulting image based on knowledge of the halftoning process used, so that compression is dependent on the halftoning process generating the image data and thus this teaching is inapplicable in a system where all that is supplied to the coder is the bilevel image, and the coder has no control over the halftoning process.
Consequently, it is desirable, and an object of the present invention, to provide a simple and versatile technique that facilitates the efficient compression of binary halftone data representing continuous tone images by known and widely-used compression processes.